import re
import random
from demo import *
import sys

def first(x)  : return x[0]
def second(x) : return x[1]

def prin(*lst) :
  out = ''.join(map(str,lst))
  sys.stdout.write(out)

def rows(file, bad=r'["\' \t\r\n]',sep=',') :
  for line in open(file,'r') :
    line = re.sub(bad,"",line).split(sep)
    if line: yield line

def often(seq,max=100,
          item   = lambda x: x,
          weight = lambda x: x.priority) :
    total = 0
    for x in seq: total += weight(x)
    while True:
        max -= 1
        if max < 0 : break
        chosen = random.uniform(0, total)
        count  = 0
        for x in seq:
            count += weight(x)
            if count > chosen:
                yield item(x)
                break

def chunks(lst,width):
  n = len(lst)
  if width < 1: width=1
  if n <= width: 
    yield lst
  else:
    start  = stop = 0 
    while stop  <= n: 
      start = stop  
      stop = start + width
      while stop < n-1 and lst[stop-1] == lst[stop]: 
        stop += 1
      if stop + width >= n : 
        stop = n 
      if start==stop: break
      yield lst[start:stop]

def tiles(l,p=20) :
  out=[]
  width=len(l)*p/100
  [out.append(x[-1]) for x in chunks(l,width)]
  return out

def any(l):
   return l[random.randint(0,len(l)-1)]

def stdev(n,s,sq) :
  if n< 2: return 0
  if s*s/n > sq: return 0  #  patches a python quirk
  return ((sq-((s*s)/n))/(n-1))**0.5

def cut(l, sort=True, cohen = 0.2, enough=4):
   n = s = sq = n0 = s0 = 0
   ordered = l if not sort else sorted(l)
   for x in ordered: 
     n += 1; s += x; sq += x*x
   mu, sd  = s/n, stdev(n,s,sq)
   best, out = -1 , None
   for here,x in enumerate(ordered):
     n0  += 1 ; n1  =  n - n0
     s0  += x ; s1  =  s - s0
     if n0 >= enough:
       if n1 >= enough:
         mu0  = s0/n0 ; mu1 = s1/n1
         if abs(mu0 - mu1) > cohen * sd:
           now  = n0/n*(mu-mu0)**2 + n1/n*(mu-mu1)**2
           if now > best:
             best,out = now,here
   return out or int(n/2)

def noop(*lst,**keys): pass
